﻿#include <iostream>

#define INVALID_SCORE -0x1fffffff
#define MAX(a, b) (a > b ? a : b)

static int partMaxScore(const int* allScore, const size_t scoreSize)
{
    int cur = 0;
    int partMax = INVALID_SCORE;
    for (int i = 0; i < scoreSize; i++)
    {
        cur += allScore[i];
        partMax = MAX(partMax, cur);
        if (cur < 0)
        {
            cur = 0;
        }
    }

    return partMax;
}

/**
 * 为了保证招聘信息的质量问题，公司为每个职位设计了打分系统，打分可以是正数，也可以是负数，正数表示用户认可帖子质量，负数表示用户不认可帖子质量。
 * 打分的分数根据评价用户的等级大小不定，比如可以为-1分、10分、30分、-10分等。假设数组A记录了一条帖子所有打分记录，现在需要找出帖子曾经得到过最高
 * 的分数是多少，用于后续根据最高分数来确认需要对发帖用户做相应的惩罚或奖励。其中，最高分的定义为：用户所有打分记录中，连续打分数据之和的最大值即认为
 * 是帖子曾经获得的最高分。
 * 例如: 帖子10001010近期的打分记录是[1,1,-1,-10,11,4,-6,9,20,-10,-2], 那么该条帖子曾经到达过的最高分数为
 * 11+4+(-6)+9+20=38. 请实现一段代码，输入为帖子近期的打分记录，输出为当前帖子得到的最高分数。
 *
 * 思路：
 * 1. 本题目可以使用暴力递归，但是无法使用严格表结构，因为分数的范围有可能很大，故创建dp数组有可能会消耗大量的内存，不可行。
 * 2. 从左到右依次处理分数，定义两个变量cur，max, cur用于累加分数，max来记录当前最大的分数。
 * 当cur累加的分数小于0，则说明当前索引以及之前的和肯定不是最大的，则cur清零继续处理下一个索引。
 */
int main_MaxOfALengthOfContinuousNumbers()
{
    int score[] = { -5,-5,-6,-8,-2,-10,1,0,1,-4 };
    int count = sizeof(score) / sizeof(int);
    int partMax = partMaxScore(score, count);
    printf("%d", partMax);
    return 0;
}